package com.xyhuo.leetcode;

import java.util.*;

public class CanFinish {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        Map<Integer, List<Integer>> map = new HashMap<>();
        int[] noCircle = new int[numCourses];
        for (int[] prerequisite : prerequisites) {
            if (map.containsKey(prerequisite[0])) {
                map.get(prerequisite[0]).add(prerequisite[1]);
            } else {
                List<Integer> list = new ArrayList<>();
                list.add(prerequisite[1]);
                map.put(prerequisite[0], list);
            }
        }
        for (int i = 0; i < numCourses; i++) {
            boolean notExist = notExistCircle(i, new HashSet<>(), noCircle, map);
            if (!notExist) {
                return false;
            }
        }
        return true;
    }

    private boolean notExistCircle(int num, Set<Integer> path, int[] noCircle, Map<Integer, List<Integer>> map) {
        if (noCircle[num] == 1) {
            return true;
        } else if (noCircle[num] == -1) {
            return false;
        }
        if (path.contains(num)) {
            noCircle[num] = -1;
            return false;
        }
        path.add(num);
        if (map.containsKey(num)) {
            List<Integer> list = map.get(num);
            for (Integer item : list) {
                boolean notExist = notExistCircle(item, path, noCircle, map);
                if (!notExist) {
                    noCircle[item] = -1;
                    return false;
                }
            }
        }
        path.remove(num);
        noCircle[num] = 1;
        return true;
    }

    public static void main(String[] args) {
        CanFinish c = new CanFinish();
//        int[][] pre = {{1, 0}, {1, 2}, {0, 1}};
//        c.canFinish(3, pre);

        int[][] pre = {{1, 4}, {2, 4}, {3, 1}, {3, 2}};
        c.canFinish(5, pre);
    }
}
